"""
难度：中等
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
"""
class Solution:
    # 暴力破解
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for i in matrix:
            for j in i:
                if j == target:
                    return True
                elif j > target:
                    return False
        return False

    # 贪心算法
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        line = len(matrix) -1
        row = len(matrix[0]) -1
 
        i = j = 0
        while True:
            if matrix[i][j] == target:
                return True

            elif i < line and matrix[i+1][j] <= target:
                i += 1
            elif j < row and matrix[i][j+1] <= target:
                j += 1
            else:
                return False

    # 二分查找
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        line = len(matrix)
        row = len(matrix[0])
        left = 0
        right = line * row
        
        while left < right:
            i, j = divmod((left + right) // 2, row)
            if matrix[i][j] == target:
                return True
            if matrix[i][j] < target:
                left = i * row + j + 1
            else:
                right = i * row +j
        return False
        
